#include "SortTestHelper.h"
#include "Student.h"
//#include "MergeSort.h"
#include "QuickSort.h"
using namespace SortTestHelper;

template<typename T>
void shellSort(T arr[], int n){

    int h = 1;
    while( h < n/3 )
        h = 3 * h + 1;
    // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...

    while( h >= 1 ){

        // h-sort the array
        for( int i = h ; i < n ; i ++ ){

            // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
            T e = arr[i];
            int j;
            for( j = i ; j >= h && e < arr[j-h] ; j -= h )
                arr[j] = arr[j-h];
            arr[j] = e;
        }

        h /= 3;
    }
}

template<typename T>
void bubbleSortOpt( T arr[] , int n){

    bool swapped;
    //int newn; // 理论上,可以使用newn进行优化,但实际优化效果较差
    do{
        swapped = false;
        //newn = 0;
        for( int i = 1 ; i < n ; i ++ )
            if( arr[i-1] > arr[i] ){
                swap( arr[i-1] , arr[i] );
                swapped = true;

                // 可以记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                // 实际优化效果较差,因为引入了newn这个新的变量
                //newn = n;
            }
        //n = newn;
        // 优化,每一趟Bubble Sort都将最大的元素放在了最后的位置
        // 所以下一次排序,最后的元素可以不再考虑
        // 理论上,newn的优化是这个优化的复杂版本,应该更有效
        // 实测,使用这种简单优化,时间性能更好
        n --;
    }while(swapped);
}

template<typename T>
void bubbleSort(T arr[], int n){

    for(int i = 0 ; i < n-1 ; i ++){
        for (int j=1; j<n-i; j++)
            if (arr[j] < arr[j-1])
                swap(arr[j], arr[j-1]);
    }

}


template<typename T>
void insertionSort(T arr[], int n){

    for(int i = 1 ; i < n ; i ++){
        // 寻找arr[i]的合适插入位置
        T e = arr[i];
        int j; //保存初始位置
        for(j=i; j>0 && arr[j-1]>e; j--){
            arr[j] = arr[j-1];
        }
        arr[j] = e;
    }

}

template<typename T>
void selectionSort(T arr[], int n){

    for(int i = 0 ; i < n ; i ++){
        // 寻找[i, n)区间里的最小值
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }

}

int main(int argc, char *argv[])
{
    int n = 100000;
    int* arr = SortTestHelper::generateRandomArray(n, 0, 10);
    //int* arr = SortTestHelper::generateNearlyOderedArray(n, 100);
    int* arr2 = SortTestHelper::copyArray(arr, n);
    int* arr3 = SortTestHelper::copyArray(arr, n);
    int* arr4 = SortTestHelper::copyArray(arr, n);
    int* arr5 = SortTestHelper::copyArray(arr, n);
    int* arr6 = SortTestHelper::copyArray(arr, n);
    //Student d[4] = {{"D", 90}, {"C", 100}, {"B", 95}, {"A", 85}};

    //selectionSort(arr, n);
    //SortTestHelper::printArray(arr, n);
    //SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);
    //SortTestHelper::testSort("Insertion Sort", insertionSort, arr2, n);
    //SortTestHelper::testSort("Bubble Sort", bubbleSortOpt, arr3, n);
    SortTestHelper::testSort("Shell Sort", shellSort, arr4, n);
    SortTestHelper::testSort("Merge Sort", mergeSort, arr5, n);
    SortTestHelper::testSort("Quick Sort", quickSort, arr6, n);
    delete[] arr;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    delete[] arr5;
    delete[] arr6;

    cout<<"Nearly ordered test"<<endl;
    int swapTimes = 100;
    arr = SortTestHelper::generateNearlyOderedArray(n, swapTimes);
    arr2 = SortTestHelper::copyArray(arr, n);
    arr3 = SortTestHelper::copyArray(arr, n);
    arr4 = SortTestHelper::copyArray(arr, n);
    arr5 = SortTestHelper::copyArray(arr, n);
    arr6 = SortTestHelper::copyArray(arr, n);
    //SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);
    //SortTestHelper::testSort("Insertion Sort", insertionSort, arr2, n);
    //SortTestHelper::testSort("Bubble Sort", bubbleSortOpt, arr3, n);
    SortTestHelper::testSort("Shell Sort", shellSort, arr4, n);
    SortTestHelper::testSort("Merge Sort", mergeSort, arr5, n);
    SortTestHelper::testSort("Quick Sort", quickSort, arr6, n);
    delete[] arr;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    delete[] arr5;
    delete[] arr6;
    return 0;
}
